package q1175_numPrimeArrangements;

import java.util.Arrays;

public class Solution {
    /*
    实际上属于一个数学问题：
    如果考虑不同位置数字的摆放 首先是质数必须要在质数索引的位置上 假设此时有m个质数
    那么此时摆放的方式有m!种方式  而其他的数同样的有(n - m)!种摆放方式 两者相乘即为答案

    如果要计算小于n的数字中有多少个质数 则需要如204题中的 埃式筛法
    需要注意的是204题中考虑的是 小于n 的范围 此题则需要包括n 所以需要countPrimes(n + 1)
     */

    static final int MOD = 1000000007;
    public int numPrimeArrangements(int n) {
        int primes = countPrimes(n + 1);
        return (int) (fac(primes) * fac(n - primes) % MOD);
    }

    private long fac(int nums) {
        long res = 1;
        for (int i = 1; i <= nums; i++) {
            res *= i;
            res %= MOD;
        }
        return res;
    }

    public int countPrimes(int n) {

        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                // 注意要用long
                if ((long) i * i < n) {
                    // 注意 这里的标法是直接从 i * i开始 然后每次 +i 进行标记
                    // 而不是从2i 3i 。。。 反复标记
                    // 因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
}
